#include <dbg.h>

#include <cassert>

using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.size();
        int resL = -1;  // 结果窗口
        int resR = n;

        vector<int> cntS(128, 0);
        vector<int> cntT(128, 0);
        for (auto c : t) {  // 统计 t 中每个字符出现的次数
            ++cntT[c];
        }

        int left = 0;
        for (int right = 0; right < n; ++right) {
            ++cntS[s[right]];
            while (isCovered(cntS, cntT)) {
                if (right - left < resR - resL) {  // 更新最小窗口
                    resL = left;
                    resR = right;
                }
                --cntS[s[left]];
                ++left;
            }
        }
        return resL == -1 ? "" : s.substr(resL, resR - resL + 1);
    }

private:
    bool isCovered(vector<int>& cntS, vector<int>& cntT) {
        for (int i = 'A'; i <= 'Z'; i++) {  // 65 - 90
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        for (int i = 'a'; i <= 'z'; i++) {  // 97 - 122
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        return true;
    }
};

int main() {
    Solution s;

    string s1 = "ADOBECODEBANC";
    string s2 = "a";
    string s3 = "a";

    string t1 = "ABC";
    string t2 = "a";
    string t3 = "aa";

    assert(s.minWindow(s1, t1) == "BANC");
    assert(s.minWindow(s2, t2) == "a");
    assert(s.minWindow(s3, t3) == "");

    return 0;
}